Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра
С А П Р
З в і т
про виконання
лабораторної роботи №2
на тему:
«ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ»
З курсу:
«Організація баз даних і знань»
Виконав:
ст. гр. КН-4
Львів 2007р.
Мета роботи
Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. МЕТОД ПРЯМОГО ДОСТУПУ
Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа. Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла.
ЕФЕКТИВНІСТЬ ДОСТУПУ дорiвнює одиницi.
ЕФЕКТИВНІСТЬ ЗБЕРІГАННЯ залежить вiд густини ключiв. Якщо густина низька, пам’ять використовується неефективно, оскiльки резервуються адреси, що вiдповiдають вiдсутнiм ключам. У цьому випадку доцiльно використовувати для органiзацiї файла метод хешування. Пряму адресацiю можна важати частковим випадком методу хешування.
2.2. МЕТОДИ ХЕШУВАННЯ.
На практицi кiлькiсть можливих значень ключiв набагато перевищує кiлькiсть реально присутнiх у будь-який момент значень цього ключа. У цьому випадку пряма адресацiя є невигiдною, оскiльки надто багато пам’ятi резервується для записiв, яких немає i нiколи не буде у файлi. Метод хешування дає змогу уникнути цього i водночас зберегти ефективнiсть, властиву прямiй адресацiї. На основi iнформацiї про множину фактичних значень ключiв створюється файл прямого доступу з такою кiлькiстю записiв, яка дещо перевищує фактичне значення ключiв. Вибирається функцiя хешування, яка перетворює значення ключа кожного запису в адресу блока у файлi. Зрозумiло, що хеш-функцiя h - це функцiя, яка вiдображає принцип "багато в один".
2.2.1. ПОШУК
Для того щоб за даним значенням ключа k знайти вiдповiдний запис, необхiдно визначити h(k) i потiм органiзувати лiнiйний пошук у блоцi, номер якого дорiвнює h(k). Цей пошук буде продовжуватися доти, поки не буде знайдений запис, значення первинного ключа якого збiгається iз заданим.
2.2.2. ВСТАВЛЯННЯ
Щоб вставити у файл новий запис, потрiбно за допомогою методу лiнiйного пошуку у блоцi, номер якого визначається значенням h(k), знайти вiльне мiсце. Пiсля цього на мiсце знайденого вiльного запису необхiдно розмiстити новий. Якщо при спробi помiстити новий запис у файл виявляється, що у знайденому блоцi немає вiльного мiсця, вважають, що блок переповнений.
2.2.3. ВИДАЛЕННЯ
Для видалення запису iз файла потрiбно, використовуючи метод лiнiйного пошуку, знайти запис у блоцi, номер якого дорiвнює h(k). Якщо запис буде знайдено то вiн видаляється, якщо нi, то очевидно, що блок був переповнений i необхiдно продовжити пошук.
2.2.4. МОДИФІКАЦІЯ
Якщо необхiдно модифiкувати запис, то потрiбно знайти цей запис i замiнити старi поля на новi. Нiяких iнших змiн не потрiбно.
ХЕШ-функція
0
1
2
3
4
5
6
7
8
9
10
К1
К12
Рис.1. Ілюстрацiя методу хешування
2.3. ПЕРЕПОВНЕННЯ
Для боротьби з переповненням можуть бути використанi три методи: зв’язаних блокiв, зв’язаних записiв та прогресуючого переповнення. 3.1. Метод блокiв, зв’язаних у ланцюг, полягає у такому. Коли блок переповнюється, у ньому розмiщується вказiвник на новостворений блок, призначений тiльки для записiв, що не помiстилися до першого блока. Якщо ж новостворений блок, своєю чергою, переповнений, у нього розмiщується вказiвник, що посилається на ще один знову створений блок i т.д. У результатi буде створений зв’язаний список блокiв, для всiх записiв якого значення функцiї хешування однакове. Головний недолiк методу зв’заних блокiв по...
